package com.github.yangyishe.p200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 120. 三角形最小路径和
 * https://leetcode.cn/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 *
 * 输入：triangle = [[-10]]
 * 输出：-10
 *
 *
 * 提示：
 *
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -104 <= triangle[i][j] <= 104
 *
 *
 * 进阶：
 *
 * 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
 */
public class Problem120 {
    public static void main(String[] args) {
        List<List<Integer>> triangle=Arrays.asList(
          Arrays.asList(2),
          Arrays.asList(3,4),
          Arrays.asList(6,5,7),
          Arrays.asList(4,1,8,3)
        );

        Problem120 problem120 = new Problem120();
        int minimumTotal = problem120.minimumTotal(triangle);
        System.out.println("minimumTotal = " + minimumTotal);

    }

    /**
     * 思路:
     * 本题,高层次可以参考低层次的选择,而不影响低层次的结果,因而可以考虑使用动态规划.
     * 以实例1为例.
     * lv=1, minSum=2
     * lv=2, minSum=2+3
     * lv=3, minSum=2+3+5
     * lv=4, minSum=2+3+5+1
     *
     * 可以创建一个,与原来三角形大小相等的三角形,实际容纳的元素是,以同位置元素为终点的最小路径和.
     * 在lv=1时,就是元素自身.
     * 在lv>=2时, 每个位置的定尾最小路径和,等于其上可能的1~2条定尾最小路径和中的最小的一条, 加上当前元素
     * 整个三角形的最小路径和, 就是最大层次中的最小定尾路径和
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        //1. 创建定尾最小路径和空三角
        List<List<Integer>> tailMinSumList=new ArrayList<>();
        tailMinSumList.add(Arrays.asList(triangle.get(0).get(0)));

        //2. 遍历推进
        for(int row=1;row<triangle.size();row++){
            List<Integer> currentList=new ArrayList<>();
            for(int col=0;col<row+1;col++){
                int leftParent=col-1>=0?tailMinSumList.get(row-1).get(col-1):Integer.MAX_VALUE;
                int rightParent=col<row?tailMinSumList.get(row-1).get(col):Integer.MAX_VALUE;
                currentList.add(Integer.min(leftParent,rightParent)+triangle.get(row).get(col));
            }
            tailMinSumList.add(currentList);
        }

        //3. 获取结果
        int result=Integer.MAX_VALUE;
        for(int minSum:tailMinSumList.get(tailMinSumList.size()-1)){
            result=Integer.min(result,minSum);
        }

        return result;
    }
}
